import sortedcontainers
class Solution(object):
    def maxBuilding(self, n, restrictions):
        st = sortedcontainers.SortedList()
        restrictions.sort(key = lambda x: x[1])
        st.add([0, 0])
        for id, height in restrictions:
            id -= 1
            r = st.bisect_right([id, 10 ** 9])
            if r > 0:
                height = min(height, st[r - 1][1] + id - st[r - 1][0])
            if r < len(st):
                height = min(height, st[r][1] + st[r][0] - id)
            st.add([id, height])
        max_height = 0
        for index in range(1, len(st)):
            id_count = abs(st[index][0] - st[index - 1][0]) + 1
            high = max(st[index][1], st[index - 1][1])
            low = min(st[index][1], st[index - 1][1])
            diff = high - low + 2
            if id_count > diff:
                high += (id_count - diff + 1) // 2
            max_height = max(max_height, high)
        max_height = max(max_height, st[-1][1] + n - 1 - st[-1][0])
        return max_height

data = Solution()
# n = 5
# restrictions = [[2,1],[4,1]]
n = 10
restrictions = [[6,0],[5,2],[7,0],[9,1],[2,4],[3,4],[4,0],[8,2],[10,0]]
print(data.maxBuilding(n, restrictions))